home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / CODECS.ZIP / codecs / francais / codhuff.c next >
Encoding:
C/C++ Source or Header  |  1995-10-13  |  14.0 KB  |  356 lines
  1. /* Fichier: codhuff.c
  2.    Auteur: David Bourgin
  3.    Date de creation: 7/2/94
  4.    Date de derniere mise a jour: 24/7/95
  5.    Dessein: Exemple de codage Huffman avec comme donnees a compresser le contenu d'un fichier.
  6.    Attention: Le compilateur doit etre configure pour une pile d'au moins 20 ko.
  7. */
  8.  
  9. #include <stdio.h>
  10. /* Pour les routines fgetc,fputc,fwrite et rewind */
  11. #include <memory.h>
  12. /* Pour les routines memset,memcpy */
  13. #include <malloc.h>
  14. /* Pour la routine malloc et free */
  15. #include <stdlib.h>
  16. /* Pour les routines qsort et exit */
  17.  
  18. /* Codes d'erreur renvoyes a l'appelant */
  19. #define NO_ERROR      0
  20. #define BAD_FILE_NAME 1
  21. #define BAD_ARGUMENT  2
  22. #define BAD_MEM_ALLOC 3
  23.  
  24. /* Constantes pratiques */
  25. #define FALSE 0
  26. #define TRUE  1
  27.  
  28. /* Variables globales */
  29. FILE *f_source,*f_dest;
  30.  
  31. typedef struct s_arbre { unsigned int octet;
  32.                              /* Un octet est volontairement code comme un entier non signe pour qu'un noeud fictif puisse depasser la valeur 255 */
  33.                          unsigned long int poids;
  34.                          struct s_arbre *ptr_gauche,
  35.                                         *ptr_droit;
  36.                        } t_arbre,*p_arbre;
  37. #define OCTET_ARBRE(ptr_arbre)  ((*(ptr_arbre)).octet)
  38. #define POIDS_ARBRE(ptr_arbre)  ((*(ptr_arbre)).poids)
  39. #define PGAUCHE_ARBRE(ptr_arbre)  ((*(ptr_arbre)).ptr_gauche)
  40. #define PDROIT_ARBRE(ptr_arbre)  ((*(ptr_arbre)).ptr_droit)
  41.  
  42. typedef struct { unsigned char bits[32];
  43.                  unsigned int nb_bits;
  44.                } t_val_bin;
  45. #define BITS_VAL_BIN(val_bin)  ((val_bin).bits)
  46. #define NB_BITS_VAL_BIN(val_bin)  ((val_bin).nb_bits)
  47.  
  48.                              /* Puisque fgetc=EOF uniquement apres un acces
  49.                                 alors statut_octet_stocke vaut TRUE si un octet a ete engrange par fgetc
  50.                                 ou FALSE s'il n'y aucun octet valide, deja lu et non traite dans val_octet_stocke */
  51. int statut_octet_stocke=FALSE;
  52. int val_octet_stocke;
  53.  
  54. /* Pseudo procedures */
  55. #define debut_des_donnees()  { (void)rewind(f_source); statut_octet_stocke=FALSE; }
  56. #define fin_des_donnees() (statut_octet_stocke?FALSE:!(statut_octet_stocke=((val_octet_stocke=fgetc(f_source))!=EOF)))
  57. #define lire_octet()  (statut_octet_stocke?statut_octet_stocke=FALSE,(unsigned char)val_octet_stocke:(unsigned char)fgetc(f_source))
  58. #define ecrire_octet(octet)  ((void)fputc((octet),f_dest))
  59.  
  60. unsigned char nb_bits_a_ecrire=0;
  61. unsigned int val_a_ecrire=0;
  62.  
  63. void ecrire_val_bin(val_bin)
  64. /* Parametres en sortie: Aucun
  65.    Action: Ecrit dans le fichier de sortie la valeur codee en binaire dans 'val_bin'
  66.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
  67. */
  68. t_val_bin val_bin;
  69. { unsigned char pos_bin,
  70.                 pos_octet;
  71.  
  72.   pos_octet=(NB_BITS_VAL_BIN(val_bin)+7) >> 3;
  73.   pos_bin=NB_BITS_VAL_BIN(val_bin) & 7;
  74.   if (pos_bin)
  75.      { pos_octet--;
  76.        val_a_ecrire=(val_a_ecrire<<pos_bin)|BITS_VAL_BIN(val_bin)[pos_octet];
  77.        nb_bits_a_ecrire += pos_bin;
  78.        if (nb_bits_a_ecrire>=8)
  79.           { nb_bits_a_ecrire -= 8;
  80.             ecrire_octet((unsigned char)(val_a_ecrire>>nb_bits_a_ecrire));
  81.             val_a_ecrire &= ((1<<nb_bits_a_ecrire)-1);
  82.           }
  83.      }
  84.   while (pos_octet)
  85.         { pos_octet--;
  86.           val_a_ecrire=(val_a_ecrire<<8)|BITS_VAL_BIN(val_bin)[pos_octet];
  87.           ecrire_octet((unsigned char)(val_a_ecrire>>nb_bits_a_ecrire));
  88.           val_a_ecrire &= ((1<<nb_bits_a_ecrire)-1);
  89.         }
  90. }
  91.  
  92. void completer_codage()
  93. /* Parametres en sortie: Aucun
  94.    Action: Complete le dernier octet a inscrire dans le fichier de codes
  95.    par une serie de bits a 0.
  96.    Erreurs: Aucune
  97. */
  98. { if (nb_bits_a_ecrire)
  99.      ecrire_octet(val_a_ecrire << (8-nb_bits_a_ecrire));
  100. }
  101.  
  102. void ecrire_en_tete(table_codes)
  103. /* Parametres en sortie: Aucun
  104.    Action: Ecrit l'en-tete dans le flux de codes
  105.    Erreurs: Aucune
  106. */
  107. t_val_bin table_codes[257];
  108. { register unsigned int i,j;
  109.   t_val_bin val_bin_a_0,
  110.             val_bin_a_1,
  111.             val_bin;         /* Sert a l'envoi en mode binaire via ecrire_val_bin */
  112.  
  113.   *BITS_VAL_BIN(val_bin_a_0)=0;
  114.   NB_BITS_VAL_BIN(val_bin_a_0)=1;
  115.   *BITS_VAL_BIN(val_bin_a_1)=1;
  116.   NB_BITS_VAL_BIN(val_bin_a_1)=1;
  117.   for (i=0,j=0;j<=255;j++)
  118.       if NB_BITS_VAL_BIN(table_codes[j])
  119.          i++;
  120.                              /* A partir d'ici i contient  le nombre d'octets differents d'occurrences non nulles a coder */
  121.                              /* Premiere partie de l'en-tete: Specifier les octets qui apparaissent dans la source de codage */
  122.   if (i<32)
  123.      {                       /* Codage des octets apparus par une serie d'octets */
  124.        ecrire_val_bin(val_bin_a_0);
  125.        NB_BITS_VAL_BIN(val_bin)=5;
  126.        *BITS_VAL_BIN(val_bin)=(unsigned char)(i-1);
  127.        ecrire_val_bin(val_bin);
  128.        NB_BITS_VAL_BIN(val_bin)=8;
  129.        for (j=0;j<=255;j++)
  130.            if NB_BITS_VAL_BIN(table_codes[j])
  131.               { *BITS_VAL_BIN(val_bin)=(unsigned char)j;
  132.                 ecrire_val_bin(val_bin);
  133.               }
  134.      }
  135.   else {                     /* Codage des octets apparus par une serie de bits */
  136.          ecrire_val_bin(val_bin_a_1);
  137.          for (j=0;j<=255;j++)
  138.              if NB_BITS_VAL_BIN(table_codes[j])
  139.                 ecrire_val_bin(val_bin_a_1);
  140.              else ecrire_val_bin(val_bin_a_0);
  141.      }
  142.                              /* Seconde partie de l'en-tete: Specifier le codage des octets (fictifs ou non) qui apparaissent dans la source de codage */
  143.   for (i=0;i<=256;i++)
  144.       if (j=NB_BITS_VAL_BIN(table_codes[i]))
  145.          { if (j<33)
  146.               { ecrire_val_bin(val_bin_a_0);
  147.                 NB_BITS_VAL_BIN(val_bin)=5;
  148.               }
  149.            else { ecrire_val_bin(val_bin_a_1);
  150.                   NB_BITS_VAL_BIN(val_bin)=8;
  151.                 }
  152.            *BITS_VAL_BIN(val_bin)=(unsigned char)(j-1);
  153.            ecrire_val_bin(val_bin);
  154.            ecrire_val_bin(table_codes[i]);
  155.          }
  156. }
  157.  
  158. int comp_poids_arbre(arbre1,arbre2)
  159. /* Parametres en sortie: Renvoie un statut de comparaison
  160.    Action: Renvoie un nombre negatif, nul ou positif selon que le poids
  161.    de 'arbre2' est inferieur, egal ou superieur au poids de 'arbre1'
  162.    Erreurs: Aucune
  163. */
  164. p_arbre *arbre1,*arbre2;
  165. { return (POIDS_ARBRE(*arbre2) ^ POIDS_ARBRE(*arbre1))?((POIDS_ARBRE(*arbre2)<POIDS_ARBRE(*arbre1))?-1:1):0;
  166. }
  167.  
  168. void supprimer_arbre(arbre)
  169. /* Parametres en sortie: Aucun
  170.    Action: Supprime la memoire allouee a un arbre
  171.    Erreurs: Aucune si l'arbre a ete construit par allocations dynamiques!
  172. */
  173. p_arbre arbre;
  174. { if (arbre!=NULL)
  175.      { supprimer_arbre(PGAUCHE_ARBRE(arbre));
  176.        supprimer_arbre(PDROIT_ARBRE(arbre));
  177.        free(arbre);
  178.      }
  179. }
  180.  
  181. p_arbre creer_arbre_codage()
  182. /* Parametres en sortie: Renvoie un arbre de codage
  183.    Action: Genere un arbre de codage de Huffman suivant les donnees issues du flux a compresser
  184.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
  185. */
  186. { register unsigned int i;
  187.   p_arbre table_occurrences[257],
  188.           ptr_arbre_fictif;
  189.  
  190.                              /* Initialiser le nombre d'occurrences de tous les octets a 0 */
  191.   for (i=0;i<=256;i++)
  192.       { if ((table_occurrences[i]=(p_arbre)malloc(sizeof(t_arbre)))==NULL)
  193.            { for (;i;i--)
  194.                  free(table_occurrences[i-1]);
  195.              exit(BAD_MEM_ALLOC);
  196.            }
  197.         OCTET_ARBRE(table_occurrences[i])=i;
  198.         POIDS_ARBRE(table_occurrences[i])=0;
  199.         PGAUCHE_ARBRE(table_occurrences[i])=NULL;
  200.         PDROIT_ARBRE(table_occurrences[i])=NULL;
  201.       }
  202.                              /* Valider les occurrences de table_occurrences en fonction des donnees a compresser */
  203.   if (!fin_des_donnees())
  204.      { while (!fin_des_donnees())
  205.              { i=lire_octet();
  206.                POIDS_ARBRE(table_occurrences[i])++;
  207.              }
  208.        POIDS_ARBRE(table_occurrences[256])=1;
  209.                              /* Tri de la table des occurrences selon le poids de chaque caractere */
  210.        (void)qsort(table_occurrences,257,sizeof(p_arbre),comp_poids_arbre);
  211.        for (i=256;(i!=0)&&(!POIDS_ARBRE(table_occurrences[i]));i--)
  212.            free(table_occurrences[i]);
  213.        i++;
  214.                              /* A partir d'ici i donne le nombre d'octets differents d'occurrence non nulle dans le flux a compresser */
  215.        while (i>0)           /* Parcourir (i+1)/2 fois la table des occurrences pour relier les noeuds en un unique arbre */
  216.              { if ((ptr_arbre_fictif=(p_arbre)malloc(sizeof(t_arbre)))==NULL)
  217.                   { for (i=0;i<=256;i++)
  218.                         supprimer_arbre(table_occurrences[i]);
  219.                     exit(BAD_MEM_ALLOC);
  220.                   }
  221.                OCTET_ARBRE(ptr_arbre_fictif)=257;
  222.                POIDS_ARBRE(ptr_arbre_fictif)=POIDS_ARBRE(table_occurrences[--i]);
  223.                PGAUCHE_ARBRE(ptr_arbre_fictif)=table_occurrences[i];
  224.                if (i)
  225.                   { i--;
  226.                     POIDS_ARBRE(ptr_arbre_fictif) += POIDS_ARBRE(table_occurrences[i]);
  227.                     PDROIT_ARBRE(ptr_arbre_fictif)=table_occurrences[i];
  228.                   }
  229.                else PDROIT_ARBRE(ptr_arbre_fictif)=NULL;
  230.                table_occurrences[i]=ptr_arbre_fictif;
  231.                (void)qsort((char *)table_occurrences,i+1,sizeof(p_arbre),comp_poids_arbre);
  232.                if (i)        /* Reste-t-il un noeud dans la table des occurrences? */
  233.                   i++;       /* Oui, alors tenir compte du noeud fictif */
  234.              }
  235.      }
  236.   return (*table_occurrences);
  237. }
  238.  
  239. void coder_table_codes(arbre,table_codes,val_code)
  240. /* Parametres en sortie: Les donnees de 'table_codes' peuvent avoir ete modifiees
  241.    Action: Enregistre l'arbre de codage sous forme d'une table de codages binaires plus rapides d'acces
  242.    'val_code' fournit le codage au noeud courant de l'arbre
  243.    Erreurs: Aucune
  244. */
  245. p_arbre arbre;
  246. t_val_bin table_codes[257],
  247.           *val_code;
  248. { register unsigned int i;
  249.   t_val_bin tmp_val_code;
  250.  
  251.   if (OCTET_ARBRE(arbre)==257)
  252.      { if (PGAUCHE_ARBRE(arbre)!=NULL)
  253.                              /* Les sous-arbres a gauche debutent par un bit a 1 */
  254.           { tmp_val_code = *val_code;
  255.             for (i=31;i>0;i--)
  256.                 BITS_VAL_BIN(*val_code)[i]=(BITS_VAL_BIN(*val_code)[i] << 1)|(BITS_VAL_BIN(*val_code)[i-1] >> 7);
  257.             *BITS_VAL_BIN(*val_code)=(*BITS_VAL_BIN(*val_code) << 1) | 1;
  258.             NB_BITS_VAL_BIN(*val_code)++;
  259.             coder_table_codes(PGAUCHE_ARBRE(arbre),table_codes,val_code);
  260.             *val_code = tmp_val_code;
  261.           }
  262.        if (PDROIT_ARBRE(arbre)!=NULL)
  263.                              /* Les sous-arbres a droite debutent par un bit a 0 */
  264.           { tmp_val_code = *val_code;
  265.             for (i=31;i>0;i--)
  266.                 BITS_VAL_BIN(*val_code)[i]=(BITS_VAL_BIN(*val_code)[i] << 1)|(BITS_VAL_BIN(*val_code)[i-1] >> 7);
  267.             *BITS_VAL_BIN(*val_code) <<= 1;
  268.             NB_BITS_VAL_BIN(*val_code)++;
  269.             coder_table_codes(PDROIT_ARBRE(arbre),table_codes,val_code);
  270.             *val_code = tmp_val_code;
  271.           }
  272.      }
  273.   else table_codes[OCTET_ARBRE(arbre)] = *val_code;
  274. }
  275.  
  276. void creer_table_codes(arbre,table_codes)
  277. /* Parametres en sortie: Les donnees de 'table_codes' peuvent avoir ete modifiees
  278.    Action: Enregistre l'arbre de codage sous forme d'une table de codages binaires plus rapide d'acces
  279.    Erreurs: Aucune
  280. */
  281. p_arbre arbre;
  282. t_val_bin table_codes[257];
  283. { t_val_bin val_code;
  284.  
  285.   (void)memset((char *)&val_code,0,sizeof(val_code));
  286.   (void)memset((char *)table_codes,0,257*sizeof(*table_codes));
  287.   coder_table_codes(arbre,table_codes,&val_code);
  288. }
  289.  
  290. void codagehuffman()
  291. /* Parametres en sortie: Aucun
  292.    Action: Compresse suivant la methode de Huffman tous les octets lus par la fonction lire_octet
  293.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
  294. */
  295. { p_arbre arbre;
  296.   t_val_bin table_codage[257];
  297.   unsigned char octet_lu;
  298.  
  299.   if (!fin_des_donnees())    /* Generer un codage uniquement s'il y a des donnees */
  300.      { arbre=creer_arbre_codage();
  301.                              /* Creation de l'arbre binaire le mieux adapte */
  302.        creer_table_codes(arbre,table_codage);
  303.        supprimer_arbre(arbre);
  304.                              /* En deduire les codages binaires dans un tableau pour un acces plus rapide */
  305.        ecrire_en_tete(table_codage);
  306.                              /* Inscrire la definition du codage */
  307.        debut_des_donnees();  /* Compression a propremement parlee des donnees */
  308.        while (!fin_des_donnees())
  309.              { octet_lu=lire_octet();
  310.                ecrire_val_bin(table_codage[octet_lu]);
  311.              }
  312.        ecrire_val_bin(table_codage[256]);
  313.                              /* Code de fin de codage */
  314.        completer_codage();   /* Completer ce dernier octet avant fermeture du fichier, si necessaire */
  315.      }
  316. }
  317.  
  318. void aide()
  319. /* Parametres en sortie: Aucun
  320.    Action: Affiche l'aide du programme et termine son execution
  321.    Erreurs: Aucune
  322. */
  323. { printf("Cet utilitaire permet de compresser un fichier par la methode de Huffman\n");
  324.   printf("telle qu'elle est exposee dans 'La Video et Les Imprimantes sur PC'\n");
  325.   printf("\nUsage: codhuff source destination\n");
  326.   printf("source: Nom du fichier a compresser\n");
  327.   printf("destination: Nom du fichier compresse\n");
  328. }
  329.  
  330. int main(argc,argv)
  331. /* Parametres en sortie: Renvoie un code d'erreur (0=Aucune)
  332.    Action: Procedure principale
  333.    Erreurs: Detectee, traitee et un code d'erreur est renvoye si necessaire
  334. */
  335. int argc;
  336. char *argv[];
  337. { if (argc!=3)
  338.      { aide();
  339.        exit(BAD_ARGUMENT);
  340.      }
  341.   else if ((f_source=fopen(argv[1],"rb"))==NULL)
  342.           { aide();
  343.             exit(BAD_FILE_NAME);
  344.           }
  345.        else if ((f_dest=fopen(argv[2],"wb"))==NULL)
  346.                { aide();
  347.                  exit(BAD_FILE_NAME);
  348.                }
  349.             else { codagehuffman();
  350.                    fclose(f_source);
  351.                    fclose(f_dest);
  352.                  }
  353.   printf("Execution de codhuff achevee.\n");
  354.   return (NO_ERROR);
  355. }
  356.